#include <iostream>
#include <raylib.h>
#include "WaterSort.h"
static int costTable[] = {-2, 0, 2, 5, 10};
int getCnt(const std::vector<int> &cup)
{
    if(cup.empty())
    {
        return -1;
    }
    int hist[20];
    for(int & i : hist)
    {
        i = 0;
    }
    for(int i : cup)
    {
        hist[i] = 1;
    }
    int cnt = 0;
    for(int i : hist)
    {
        cnt += i;
    }
    return costTable[cnt];
}
int getCost(const PathState &pathstate)
{
    int cost = 0;
    for(const auto & i : pathstate.state.water)
    {
        cost += getCnt( i);
    }
    return cost + pathstate.actions.size();
}
struct Compare {
    bool operator()(const PathState& a, const PathState& b) const {
        return getCost(a) > getCost(b);
    }
};
static void split(const std::string& s, std::vector<std::string>& tokens, const std::string& delimiters = " ")
{
    std::string::size_type lastPos = s.find_first_not_of(delimiters, 0);
    std::string::size_type pos = s.find_first_of(delimiters, lastPos);
    while (std::string::npos != pos || std::string::npos != lastPos) {
        tokens.push_back(s.substr(lastPos, pos - lastPos));//use emplace_back after C++1
        lastPos = s.find_first_not_of(delimiters, pos);
        pos = s.find_first_of(delimiters, lastPos);
    }
}
State loadStateFromString(std::string str)
{
    State state;
    std::vector<std::string> linetokens;
    split(str, linetokens,"\n");
    state.cup_num = std::stoi(linetokens[0]);
    state.capacity = std::stoi(linetokens[1]);
    std::cout<< linetokens[0]<<std::endl;
    std::cout<< linetokens[1]<<std::endl;
    std::cout<< linetokens[2]<<std::endl;
    std::cout<< linetokens[3]<<std::endl;
    for(int i = 0; i < state.cup_num; i++)
    {
        auto line = linetokens[i+2];
        std::cout<<line.size()<<std::endl;
        if(line.size() < 4)
        {
            state.empty_cup++;
            state.water.emplace_back(std::vector<int>());
        }else{
            std::vector<std::string> tokens;
            split(line, tokens);
            std::vector<int> water;
            for(int j = 0; j < tokens.size(); j++)
            {
                water.push_back(std::stoi(tokens[j]));
            }
            state.water.push_back(water);
        }
    }
    return state;
}
State loadStateFromFile(std::string filename) {
    State state;
    std::ifstream infile(filename);
    std::string line;
    std::getline(infile, line);
    state.cup_num = std::stoi(line);
    std::getline(infile, line);
    state.capacity = std::stoi(line);
    for(int i = 0; i < state.cup_num; i++)
    {
        std::getline(infile, line);
        if(line.size() == 0)
        {
            state.empty_cup++;
            state.water.emplace_back(std::vector<int>());
        }else{
            std::vector<std::string> tokens;
            split(line, tokens);
            std::vector<int> water;
            for(int j = 0; j < tokens.size(); j++)
            {
                water.push_back(std::stoi(tokens[j]));
            }
            state.water.push_back(water);
        }
    }
    return state;
}
bool isAction(int a, int b, const State &cur_state)
{
    return (a!=b) &&
           (!cur_state.water[a].empty()) &&
           (cur_state.water[b].size() < cur_state.capacity) &&
           (cur_state.water[b].empty() || cur_state.water[a].back() == cur_state.water[b].back());
}
std::vector<ActionState> get_successor(const State &cur_state)
{
    std::vector<ActionState> ASList;
    for(int i = 0; i < cur_state.cup_num; i++)
    {
        for(int j = 0; j < cur_state.cup_num; j++)
        {
            if(isAction(j,i,cur_state))
            {
                ActionState AS;
                AS.state = move({j,i},cur_state);
                AS.action = {j,i};
                ASList.emplace_back(AS);
            }
        }
    }
    return ASList;
}
State move(std::array<int,2> action, const State &cur_state)
{
    State new_state = cur_state;
    int cup1 = action[0];
    int cup2 = action[1];
    while(isAction(cup1,cup2, new_state))
    {
        int water = new_state.water[cup1].back();
        new_state.water[cup1].pop_back();
        new_state.water[cup2].push_back(water);
    }
    return new_state;
}
bool isRight(const State &cur_state)
{
    if(cur_state.water.empty())
    {
        return false;
    }
    for(int i = 0; i < cur_state.cup_num; i++)
    {
        if(cur_state.water[i].size() != 0 && cur_state.water[i].size() != cur_state.capacity)
        {
            return false;
        }
        if(cur_state.water[i].size() == cur_state.capacity)
        {
            for(int j = 0; j < cur_state.capacity; j++)
            {
                if(cur_state.water[i][j] != cur_state.water[i][0])
                {
                    return false;
                }
            }
        }
    }
    return true;
}
std::vector<int> getHash(const State &state)
{
    std::vector<int> hash;
    for(int i = 0; i < state.water.size(); i++)
    {
        auto water = state.water[i];
        for(int j = 0; j < water.size(); j++)
        {
            hash.push_back(water[j]);
        }
        hash.push_back(0);
    }
    return hash;
}
void printState(const State &state)
{
    printf("{");
    for(int i = 0; i < state.water.size(); i++)
    {
        auto water = state.water[i];
        printf("[");
        for(int j = 0; j < water.size(); j++)
        {
            printf("%d,",water[j]);
        }
        printf("]");
    }
    printf("}\n");
}
bool astar(State state, std::vector<std::array<int ,2>> &result)
{
    int ttt = 0;
    std::priority_queue<PathState, std::vector<PathState>, Compare> openlist;
    std::set< std::vector<int> > closelist;
    PathState init;
    init.state = std::move(state);
    init.actions.clear();
    openlist.push(init);
    while(!openlist.empty())
    {
        PathState cur_state = openlist.top();
//        printf("cur_state:");
//        printState(cur_state.state);
        openlist.pop();
        if(isRight(cur_state.state))
        {
            result = cur_state.actions;
            return true;
        }
        auto hash = getHash(cur_state.state);
        if(closelist.find(hash) != closelist.end())
        {
//            printf("in closelist\n");
            continue;
        }else{
            closelist.insert(hash);
        }
        auto succs = get_successor(cur_state.state);
        for(const auto& succ : succs)
        {
            PathState next_state;
            next_state.state = move(succ.action, cur_state.state);
            next_state.actions = cur_state.actions;
            next_state.actions.push_back(succ.action);
            openlist.push(next_state);
        }
        if(ttt++ > 1000000)
        {
            return false;
        }
    }
    return false;
}
bool bfs(State state, std::vector<std::array<int ,2>> &result)
{
    int ttt = 0;
    std::queue<PathState> openlist;
    std::set< std::vector<int> > closelist;
    PathState init;
    init.state = std::move(state);
    init.actions.clear();
    openlist.push(init);
    while(!openlist.empty())
    {
        PathState cur_state = openlist.front();
        printf("cur_state:");
        printState(cur_state.state);
        openlist.pop();
        if(isRight(cur_state.state))
        {
            result = cur_state.actions;
            return true;
        }
        auto hash = getHash(cur_state.state);
        if(closelist.find(hash) != closelist.end())
        {
            printf("in closelist\n");
            continue;
        }else{
            closelist.insert(hash);
        }
        auto succs = get_successor(cur_state.state);
        for(const auto& succ : succs)
        {
            PathState next_state;
            next_state.state = move(succ.action, cur_state.state);
            next_state.actions = cur_state.actions;
            next_state.actions.push_back(succ.action);
            openlist.push(next_state);
        }
        if(ttt++ > 1000000)
        {
            return false;
        }
    }
    return false;
}
State generateRandomState(int cup_num, int empty_cup, int stepnum)
{
    State state;
    state.cup_num = cup_num;
    state.capacity = 4;
    state.empty_cup = empty_cup;
    srand((unsigned int)time(NULL));
    for(int i = 0; i <cup_num; i++)
    {
        if( i < empty_cup)
        {
            state.water.emplace_back(std::vector<int>());
        }else{
            state.water.emplace_back(std::vector<int>{i,i,i,i});
        }
    }
    for(int i = 0; i < stepnum; ++i)
    {
        int a = rand() % cup_num;
        while(state.water[a].empty())
        {
            a = rand() % cup_num;
        }
        int b = rand() % cup_num;
        while(b == a || state.water[b].size() == state.capacity)
        {
            b = rand() % cup_num;
        }
        state.water[b].push_back(state.water[a].back());
        state.water[a].pop_back();
        TraceLog(LOG_INFO, "%d -> %d\n", a, b);
    }
    for(int i = 0; i < empty_cup; ++i)
    {
        while(state.water[i].size() > 0)
        {
            int a = rand() % cup_num;
            while(a <= i || state.water[a].size() == state.capacity)
            {
                a = rand() % cup_num;
            }
            state.water[a].push_back(state.water[i].back());
            state.water[i].pop_back();
            TraceLog(LOG_INFO, "%d -> %d\n", i, a);
        }
    }
    return state;
}